class Solution {
private:
    int nums[1691] = {1, 1};
public:
    int nthUglyNumber(int n) {
        int m_2 = 1, m_3 = 1, m_5 = 1;
        for(int i = 2; i <= n; i++){
            nums[i] = min(nums[m_2] * 2, min(nums[m_3] * 3, nums[m_5] * 5));
            if(nums[m_2] * 2 == nums[i])m_2++;
            if(nums[m_3] * 3 == nums[i])m_3++;
            if(nums[m_5] * 5 == nums[i])m_5++;
        }
        return nums[n];
    }
};

//2021.4.10
